﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Sorting
{
    public class InPlaceQuickSorter<T> : IInPlaceSorter<T>
    {
        private Lists.IList<T> _list;
        private Comparison<T> _comparison;

        private void Quicksort(int p, int r)
        {
            while (r - p > 1)
            {
                T pivot = _list[r - 1];
                int i = p - 1;
                for (int j = p; j < r - 1; j++)
                {
                    if (_comparison(_list[j], pivot) <= 0)
                    {
                        i++;
                        var aux = _list[i];
                        _list[i] = _list[j];
                        _list[j] = aux;
                    }
                }
                var aux2 = _list[i + 1];
                _list[i + 1] = _list[r - 1];
                _list[r - 1] = aux2;
                int pivotIndex = i + 1;
                if (r - pivotIndex < pivotIndex - p)
                {
                    Quicksort(pivotIndex, r);
                    r = pivotIndex;
                }
                else
                {
                    Quicksort(p, pivotIndex);
                    p = pivotIndex + 1;
                }
            }
        }

        #region IInPlaceSorter<T> Members

        public void Sort(Lists.IList<T> list, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            _list = list;
            Quicksort(0, list.Count);
            _list = null;
        }

        #endregion
    }

    public class BasicQuickSorter<T> : ISorter<T>
    {
        private readonly Func<IEnumerable<T>, Lists.IList<T>> _createList;

        public BasicQuickSorter(Func<IEnumerable<T>,Lists.IList<T>> createList = null)
        {
            _createList = createList ?? (it => AlgoritmiaFactory.Lists<T>.BuildDefault(it));
        }

        #region ISorter<T> Members

        public IEnumerable<T> Sorted(Lists.IList<T> list, Comparison<T> comparison = null)
        {
            comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            Func<Lists.IList<T>, IEnumerable<T>> sortRecursively = null;
            sortRecursively = a =>
                                  {
                                      if (a.Count <= 1)
                                      {
                                          return a;
                                      }
                                      var pivot = a[0];
                                      var listCopy = _createList(a);
                                      listCopy.RemoveAt(0);
                                      var left = sortRecursively(_createList(a.Where(x => comparison(x, pivot) < 0)));
                                      var right =
                                          sortRecursively(_createList(listCopy.Where(x => comparison(x, pivot) >= 0)));
                                      return left.Concat(new[] {pivot}).Concat(right);
                                  };
            return sortRecursively(list);

        }

        #endregion
    }

    public class BasicInPlaceQuickSorter<T> : IInPlaceSorter<T>
    {
        private Comparison<T> _comparison;

        protected virtual int Partition(Lists.IList<T> a, int p, int r)
        {
            var pivot = a[r - 1];
            var i = p - 1;
            for (int j = p; j < r - 1; j++)
            {
                if (_comparison(a[j], pivot) <= 0)
                {
                    i++;
                    var aux = a[i];
                    a[i] = a[j];
                    a[j] = aux;
                }
            }
            var aux2 = a[i + 1];
            a[i + 1] = a[r - 1];
            a[r - 1] = aux2;
            return i + 1;
        }

        protected virtual void Quicksort(Lists.IList<T> a, int p, int r)
        {
            if (r - p > 1)
            {
                var pivotIndex = Partition(a, p, r);
                Quicksort(a, p, pivotIndex);
                Quicksort(a, pivotIndex + 1, r);
            }
        }

        #region IInPlaceSorter<T> Members

        public void Sort(Lists.IList<T> list, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            Quicksort(list, 0, list.Count);
        }

        #endregion
    }

    public class RandomizedInPlaceQuickSorter<T> : BasicInPlaceQuickSorter<T>
    {
        protected override int Partition(Lists.IList<T> a, int p, int r)
        {
            var random = new Random(DateTime.Now.Millisecond);
            int q = random.Next(p, r);
            var aux = a[r - 1];
            a[r - 1] = a[q];
            a[q] = aux;
            return base.Partition(a, p, r);
        }
    }

    public class BasicSemiIterativeInPlaceQuickSorter<T> : RandomizedInPlaceQuickSorter<T>
    {
        protected override void Quicksort(Lists.IList<T> a, int p, int r)
        {
            while (r - p > 1)
            {
                var pivotIndex = Partition(a, p, r);
                Quicksort(a, p, pivotIndex);
                p = pivotIndex + 1;
            }
        }
    }

    public class SemiIterativeInPlaceQuickSorter1<T> : RandomizedInPlaceQuickSorter<T>
    {
        protected override void Quicksort(Lists.IList<T> a, int p, int r)
        {
            while (r - p > 1)
            {
                var pivotIndex = Partition(a, p, r);
                if (r - pivotIndex < pivotIndex - p)
                {
                    Quicksort(a, pivotIndex + 1, r);
                    r = pivotIndex;
                }
                else
                {
                    Quicksort(a, p, pivotIndex);
                    p = pivotIndex + 1;
                }
            }
        }
    }

    public class RandomizedSemiIterativeInPlaceQuickSorter<T> : IInPlaceSorter<T>
    {
        private Lists.IList<T> _a;
        private Comparison<T> _comparison;

        private void Quicksort(int p, int r)
        {
            while (r - p > 1)
            {
                var random = new Random(DateTime.Now.Millisecond);
                var q = random.Next(p, r); 
                var aux = _a[r - 1];
                _a[r - 1] = _a[q];
                _a[q] = aux;
                var pivot = _a[r - 1];
                var i = p - 1;
                for (int j = p; j < r - 1; j++)
                {
                    if (_comparison(_a[j], pivot) <= 0)
                    {
                        i++;
                        var aux2 = _a[i];
                        _a[i] = _a[j];
                        _a[j] = aux2;
                    }
                }
                var aux3 = _a[i + 1];
                _a[i + 1] = _a[r - 1];
                _a[r - 1] = aux3;
                var pivotIndex = i + 1;
                if (r - pivotIndex < pivotIndex - p)
                {
                    Quicksort(pivotIndex + 1, r);
                    r = pivotIndex;
                }
                else
                {
                    Quicksort(p, pivotIndex);
                    p = pivotIndex + 1;
                }
            }
        }

        #region IInPlaceSorter<T> Members

        public void Sort(Lists.IList<T> list, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            _a = list;
            Quicksort(0, _a.Count);
            _a = null;
        }

        #endregion
    }

    public class SemiIterativeInPlaceQuickSorter<T> : IInPlaceSorter<T>
    {
        private Lists.IList<T> _a;
        private Comparison<T> _comparison;

        private void Quicksort(int p, int r)
        {
            while (r - p > 1)
            {
                var pivot = _a[r - 1];
                var i = p - 1;
                for (var j = p; j < r - 1; j++)
                {
                    if (_comparison(_a[j], pivot) <= 0)
                    {
                        i++;
                        var aux = _a[i];
                        _a[i] = _a[j];
                        _a[j] = aux;
                    }
                }
                var aux2 = _a[i + 1];
                _a[i + 1] = _a[r - 1];
                _a[r - 1] = aux2;
                var pivotIndex = i + 1;
                if (r - pivotIndex < pivotIndex - p)
                {
                    Quicksort(pivotIndex + 1, r);
                    r = pivotIndex;
                }
                else
                {
                    Quicksort(p, pivotIndex);
                    p = pivotIndex + 1;
                }
            }
        }

        #region IInPlaceSorter<T> Members

        public void Sort(Lists.IList<T> list, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            _a = list;
            Quicksort(0, list.Count);
            _a = null;
        }

        #endregion
    }

}
